MatrixChainMultiplication.java

packagesection19_DynamicProgramming;

publicclassMatrixChainMultiplication {

// to test exact running time
publicstaticlongstart() {
returnSystem.currentTimeMillis();
 }

publicstaticlongend() {
returnSystem.currentTimeMillis();
 }

publicstaticvoidmain(String[] args) {
/*
 * matrices dimensions:
 * 
 * M1: 4 x 2
 * 
 * M2: 2 x 3
 * 
 * M3: 3 x 5
 * 
 * M4: 5 x 1
 */
int[] matricesDimensions = { 4, 2, 3, 5, 1 };
intlen = matricesDimensions.length;
intstartIndex = 0, endIndex = len - 1;

System.out.println(MCMRecursion(matricesDimensions, startIndex, endIndex)); // 29
System.out.println(MCMTopDownDP(matricesDimensions, startIndex, endIndex, newint[len][len]));
System.out.println(+MCMBottomUpDP(matricesDimensions));

System.out.println("\ntesting large input...");

int[] arr = newint[1000];
for (inti = 0; i < arr.length; i++) {
arr[i] = i + 1;
 }

intn = arr.length;

System.out.println("\ntesting top down");

longstartTime = start();
System.out.println("operations: " + MCMTopDownDP(arr, 0, n - 1, newint[n][n]));
longstopTime = end();
System.out.println("time taken: " + (stopTime - startTime) + " milliseconds");

System.out.println("\ntesting bottom up");

longstartTime2 = start();
System.out.println("operations: " + MCMBottomUpDP(arr));
longstopTime2 = end();
System.out.println("time taken: " + (stopTime2 - startTime2) + " milliseconds");

 }

publicstaticintMCMRecursion(int[] matrices, intsi, intei) {

// for single matrix
if (ei == (si + 1)) {
return0;
 }
intmin = Integer.MAX_VALUE;

for (intsplits = si + 1; splits <= ei - 1; splits++) {

intfirstHalf = MCMRecursion(matrices, si, splits); // matrices[si]*matrices[splits]
intsecondHalf = MCMRecursion(matrices, splits, ei); // matrices[splits]*matrices[ei]

intselfWork = matrices[si] * matrices[splits] * matrices[ei];
inttotal = firstHalf + secondHalf + selfWork;

if (total < min) {
min = total;
 }
 }
returnmin;
 }

publicstaticintMCMTopDownDP(int[] matrices, intsi, intei, int[][] storage) {

if (ei == (si + 1)) {
return0;
 }
if (storage[si][ei] != 0) { // reuse
returnstorage[si][ei];
 }

intmin = Integer.MAX_VALUE;

for (intsplits = si + 1; splits <= ei - 1; splits++) {

intfirstHalf = MCMTopDownDP(matrices, si, splits, storage);
intsecondHalf = MCMTopDownDP(matrices, splits, ei, storage);

intselfWork = matrices[si] * matrices[splits] * matrices[ei];
inttotal = firstHalf + secondHalf + selfWork;

if (total < min) {
min = total;
 }
 }
storage[si][ei] = min; // store

returnmin;
 }

// O(n^3) Time | O(n^2) Space
publicstaticintMCMBottomUpDP(int[] matrices) {
intn = matrices.length;
int[][] storage = newint[n][n];

// filling diagonally
for (intslide = 1; slide < n; slide++) {

for (intsi = 0; si <= n - slide - 1; si++) {
intei = si + slide;

// logic used in top down approach
if (ei == (si + 1)) {
storage[si][ei] = 0;
 } else {
intmin = Integer.MAX_VALUE;

for (intsplits = si + 1; splits <= ei - 1; splits++) {

intfirstHalf = storage[si][splits];
intsecondHalf = storage[splits][ei];

intselfWork = matrices[si] * matrices[splits] * matrices[ei];
inttotal = firstHalf + secondHalf + selfWork;

if (total < min) {
min = total;
 }
 }
storage[si][ei] = min; // store
 }
 }
 }

returnstorage[0][n - 1];
 }

}

/* output:
29
29
29

testing large input...

testing top down
operations: -2147334086
time taken: 3881 milliseconds

testing bottom up
operations: -2147334086
time taken: 1848 milliseconds
*/